package com.example.lcpractice.heading_offer;

import java.util.Arrays;
import java.util.HashSet;

/**
 * [剑指 Offer 57]和为s的两个数字.java
 * 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [2,7,11,15], target = 9
 * 输出：[2,7] 或者 [7,2]
 * 示例 2：
 * <p>
 * 输入：nums = [10,26,30,31,47,60], target = 40
 * 输出：[10,30] 或者 [30,10]
 * 限制：
 * <p>
 * 1 <= nums.length <= 10^5
 * 1 <= nums[i] <= 10^6
 * Related Topics
 * 数组
 * 双指针
 * 二分查找
 */
public class q57 {
    public static void main(String[] args) {
        int[] arr = {10, 26, 30, 31, 47, 60};
        System.out.println(Arrays.toString(twoSum3(arr, 90)));
    }

    /**
     * 时间复杂度爆表
     *
     * @param nums   目标数组
     * @param target 目标数字
     * @return 组成数组
     */
    public static int[] twoSum(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int[] targetArr = new int[2];
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                targetArr[0] = nums[left];
                targetArr[1] = nums[right];
                return targetArr;
            } else {
                right--;
            }
            if (left == right && left < nums.length - 1) {
                left++;
                right = nums.length - 1;
            }

        }
        return targetArr;

    }


    /**
     * 解题思路：
     * 利用 HashMap 可以通过遍历数组找到数字组合，时间和空间复杂度均为 O(N) ；
     * 注意本题的 nums 是 <b>排序数组</b> ，因此可使用 双指针法 将空间复杂度降低至 O(1) 。
     * <p>
     * 算法流程：
     * 初始化： 双指针 i , j 分别指向数组 nums 的左右两端 （俗称对撞双指针）。
     * 循环搜索： 当双指针相遇时跳出；
     * 计算和 s=nums[i]+nums[j] ；
     * 若 s>target ，则指针 j 向左移动，即执行 j=j−1 ；
     * 若 s<target ，则指针 i 向右移动，即执行 i=i+1 ；
     * 若 s=target ，立即返回数组 [nums[i],nums[j]] ；
     * 返回空数组，代表无和为 target 的数字组合。
     */
    public static int[] twoSum2(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int[] targetArr = new int[2];
        HashSet<Integer> integers = new HashSet<>();
        while (left < right) {
            int sumTemp = nums[left] + nums[right];
            if (sumTemp > target) {
                right--;
            } else if (sumTemp < target) {
                left++;
            } else {
                targetArr[0] = nums[left];
                targetArr[1] = nums[right];
                return targetArr;
            }

        }
        return targetArr;

    }

    public static int[] twoSum3(int[] nums, int target) {
        int lens = nums.length;
        int left;
        int right;
        // 二分查找右边界不断左移，缩小搜索范围，并默认选中最右数位第一个数
        for (int i = lens - 1; i > 0; i--) {
            left = 0;
            right = i;
            int endNum = nums[i];
            // 第一个数>=target肯定没戏，跳过
            if (endNum >= target) {
                continue;
                // 在当前区间二分查找能和选中数组合成target的另一个数
            }
            while (right > left) {
                int mid = left + (right - left) / 2;
                // 二分查找左边为小于等于的，右边为大于的，两个区间都是左闭右开
                if (nums[mid] > target - endNum) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
                // 找到一组直接返回
                if (target - nums[mid] == endNum) {
                    return new int[]{target - nums[mid], nums[mid]};
                }
            }
        }
        // 题目保证一定会搜索到，这里的return无意义
        return new int[]{0, 0};
    }

}
